Network design applies to many fields of commercial interest. One example is overnight package delivery, where packages must be delivered between cities over a network of possible air routes that have different costs. Another example is utility design, where a commodity such as electricity or water is to be distributed to geographically separate customers over a network of possible conduits that have different costs. The field of telecommunications contains several examples in which possible transmission elements, with different costs, may be combined in many different ways, between different points, in order to obtain a network of paths between the points. One example arises in the design of a fiber optic transmission network (e.g., one using fiber optic links between routers as part of an ISP network) to join geographically dispersed major cities, with possible alternate routes between cities having different costs (which may be defined in terms of the construction costs of providing the route, for example).
In each of these network examples, it is desirable to be able to employ a method or algorithm which will provide the minimum cost network by selecting, from the possible network elements, those which provide the lowest total cost. A minimum cost network designed according to such a method will allow lower cost services to customers using such a network and give a competitive advantage to the service provider using such a network.
The overall network design context may include additional considerations. For example, the network design criteria may require that the network include pairs of selected points, e.g., certain city pairs. The design problem then is to find the minimum cost network solution that contains paths between each of these paired points.
The network design criteria may further assign penalty costs if a required path between selected points is not included. An example of such a penalty cost in the package delivery context is the cost of leasing another carrier's air transport facilities for a package delivery route segment not covered by the package deliverer's own network. In the telecommunications context, an example of such a penalty cost is the cost of leasing telecommunications transmission capacity from another provider for a route segment not provided by a provider's own network. Allowing penalty costs supplies the opportunity for a lower overall cost network. The network design problem, with this additional consideration, is then to find a network solution that minimizes the total combined costs of selected network elements plus penalties incurred for having any required points unconnected by the selected elements.
Finding a network whose design considerations include a minimization of cost, the selection of elements with assigned costs, the requirement that the solution include pairs of selected points, and the allowance of assigned penalty costs if a required pair of points is not connected by the selected elements, is a design problem corresponding mathematically to the Prize Collecting Steiner Forest (PCSF) problem. Mathematically, the network of possible elements is a graph G=(V,E) where V is the set of vertices vi, vj, . . . , and E is the set of edges eij connecting vertices vi, vj, with a set of required pairs ={(s1,t1), (s2,t2), . . . (st}, a non-negative cost function c: E→Q+ (which means the function maps the set E into a set of positive rational numbers), and a non-negative penalty function π: →Q+. Each edge has a cost cij and each pair  has a penalty πk that is incurred if the pair vertices sk, tk are not connected to an edge. The goal is to find a set (or forest) H that minimizes the costs of the edges of H plus the penalties paid for pairs whose vertices are not all connected by H. In other words, the goal is a minimum-cost way of buying a set of edges and paying the penalty for those pairs which are not connected via bought edges.
A simple example of such a network is shown in FIG. 1. The graph G of potential network elements includes hollow circle vertices that are denoted with upper case letters A, B, C, D, F and J and represent cities, for example. The solid circles denoted with lower case letters a, b, c, d and f represent non-city vertices. Edges e representing transmission links, for example, that are available to be included in the network, are denoted by solid lines linking vertices as shown. Each edge eij has a cost cij. Required pairs of vertices , , , , representing cities that are required to be connected in the network, have respective penalty costs π1, π2, π3, π4, that are incurred if the vertices in the pair are not joined to a selected edge.
A minimal cost solution H to the graph G of FIG. 1 is shown in FIG. 1A, where solid lines represent edges selected from those available in FIG. 1, and dashed lines show penalty connections. The connection for required pair AB is furnished by penalty π1; for pair BC by edges Bc, cD; for pair CD by edge CD; and for pair DF by edges DC, Cc, cJ and JF.
The Prize Collecting Steiner Forest (PCSF) problem has been solved for special cases. In the special case that all sinks are identical, i.e., there is a common root r in every pair  in the PCSF problem, the problem reduces to the classic Prize-Collecting Steiner Tree problem. Bienstock, Goemans, Simchi-Levi, and Williamson [D. BIENSTOCK, M. X. GOEMANS, D. SIMCHI-LEVI, AND D. WILLIAMSON, A note on the prize collecting traveling salesman problem, Math. Programming, 59 (1993), pp. 413-420] first considered this tree problem (based on a problem earlier proposed by Balas [E. BALAS, The prize collecting traveling salesman problem, Networks, 19 (1989), pp. 621-636]) for which they gave a 3-approximation algorithm. The current best approximation algorithm for this tree problem is a primal-dual 2−1/(n−1) approximation algorithm (n is the number of vertices of the graph) due to Goemans and Williamson [M. X. GOEMANS AND D. P. WILLIAMSON, A general approximation technique for constrained forest problems, SIAM J. Comput., 24 (1995), pp. 296-317].
The general form of the PCSF problem first was formulated by Hajiaghayi and Jain [M. T. HAJIAGHAYI AND K. JAIN, The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema, in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, 2006, ACM, pp. 631-640]. They showed how by a primal-dual algorithm to a novel integer programming formulation of the problem with doubly-exponential variables, it is possible to obtain a 3-approximation algorithm for the problem. In addition, they show that the factor 3 in the analysis of their algorithm is tight. However they show how a direct randomized LP rounding algorithm with approximation factor 2.54 can be obtained for this problem. Their approach has been generalized by Sharma, Swamy, and Williamson [Y. SHARMA, C. SWAMY, AND D. P. WILLIAMSON, Approximation algorithms for prize collecting forest problems with submodular penalty functions, in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '07), Philadelphia, Pa., USA, 2007, Society for Industrial and Applied Mathematics, pp. 1275-1284] for network design problems where violated arbitrary 0-1 connectivity constraints are allowed in exchange for a very general penalty function. The work of Hajiaghayi and Jain has also motivated a game-theoretic version of the problem considered by Gupta et al. [A. GUPTA, J. K{umlaut over ( )}ONEMANN, S. LEONARDI, R. RAVI, AND G. SCH{umlaut over ( )}AFER, An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem, in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '07), Philadelphia, Pa., USA, 2007, Society for Industrial and Applied Mathematics, pp. 1153-1162].
Besides the network design criteria that are able to be considered by the PCSF problem, it may be useful to be able to impose a further network design consideration, namely that of providing a desired redundant connectivity between required points (measured in terms of numbers of required alternate edge disjoint paths between the points). For example, in order to provide for continued service in the event of a failure of a selected network element, such as breakage of a fiber optic cable, it may be required that selected points (vertices) be connected with two or more redundant edge disjoint paths (commonly referred to a k-coverage when the design is to include k redundant paths between points). An example of a method for finding such independent edge disjoint paths in a network context is shown in U.S. Pat. No. 6,928,484.
Finding a network whose design considerations include a minimization of cost, the selection of elements with assigned costs, the requirement that the solution include pairs of selected points, the requirement of multiple connectivity between selected pairs of points and the allowance of assigned penalty costs if a required pair of points is not connected by the required number of elements, is a design problem corresponding mathematically to the Prize Collecting Survivable Steiner Network (PCSSN) problem. Mathematically, the network of possible elements is a graph G=(V,E) where V is the set of vertices vi, vj, . . . and E is the set of edges eij, with a set of required pairs ={(s1,t1), (s2,t2), . . . (st}, a non-negative cost function c: E→Q+, connectivity requirements ruv for all pairs of vertices u and v, and a non-increasing non-negative marginal penalty function π: →Q+ for u and v in case we cannot satisfy all ruv. Each edge has a cost cij and each pair has a penalty πk that is incurred if the pair vertices sk,tk are not all connected by edges in accordance with connectivity requirement ruv. The goal is to find a minimum way of constructing a network (graph) H in which we connect u and v with r′u v≦ruv edge-disjoint paths and pay the marginal penalty for each of the ruv−ruv occurrences of violated connectivity between u and v.
A simple example of such a network is shown in FIG. 2. As in FIG. 1, the graph G of potential network elements includes hollow circle vertices that are denoted with upper case letters A, B, C, D, F and J and represent cities, for example. The solid circles denoted with lower case letters a, b, c, d and f represent non-city vertices. Edges e representing transmission links, for example, that are available to be included in the network are denoted by solid lines linking vertices as shown. Each edge eij has a cost cij. Required pairs of vertices , , , , representing cities that are required to be connected in the network, have connectivity requirements r1, r2, r3, r4. In the example of FIG. 2, r1, r2, r3 are each 2 and r4 is 4. Non-increasing non-negative marginal penalty costs π11 and π21, for r1;π21 and π22 for r2; π31 and π31 for r3; and π41, π42, π43 and π44 for r4 are available to be incurred for each instance in which we fail to satisfy a required pair's connectivity requirement with selected edges.
A minimum cost solution H to the graph G of FIG. 2 is shown in FIG. 2A, where solid lines represent edges selected from those available in FIG. 2, and dashed lines show penalty connections. The 2-fold connection for required pair AB is furnished by penalty π11 and edges Ab, bB; for pair BC by penalty π21 and edges Bc, cD; for pair CD by edge CD and edges Cd, dD; and the 4-fold connection for pair DF is furnished by two penalties π41, π42; edges DC, Cc, cJ, JF; and edges Dd, df, fF.
When all connectivity requirements ruv are 1, the PCSSN problem reduces to the PCSF problem described above. When all penalties π are ∞, the PCSSN problem reduces to the special case of the classic survivable Steiner network design problem. For this problem, Jain [K. JAIN, A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica, 21 (2001), pp. 39-60], using the method of iterative rounding, obtained a 2-approximation algorithm, improving on a long line of earlier research that applied primal-dual methods to this problem.
Jain's iterative rounding approach has been limited to the non-prize collecting context of the classic problem he addresses, with no provision for penalties, and does not provide feasible solutions to the Prize Collecting Survivable Steiner Network problem, which heretofore have not been found.
The chief problem encountered in finding an optimum network design solution in context of PCSF and PCSSN is that for all but trivial configurations, which means that for all configurations actually encountered in the real world of network design, methods providing exact solutions may be devised but they are not feasible because they require too much time to compute. For example, it would be possible to obtain an exact solution by making a brute force comparison of the costs of all possible network element permutations but years of computation time would be needed for routinely complex networks. Accordingly, methods providing approximate solutions have been sought. Approximation methods have, for the most part, used linear program solving techniques to solve optimization problems in which the variables correspond to the physical attributes (locations, connection cost, penalties, connectivity) of the network elements. However, approximation methods often must make limiting assumptions in order to be solvable using known ellipsoidal or flow-based LP-solver techniques. Additionally, approximation algorithms must provide some measure of how closely the approximate solution is to an optimal solution, which means that an approximation solution must be mathematically demonstrated to be within a factor p of the optimum solution (such an algorithm is referred to as a p-approximation algorithm). To prove the approximation has a specified degree of accuracy, limiting assumptions may be made that may reduce the generality of the methods in dealing with actual design applications.
Thus approximation methods must find a suitable balance among three considerations: the computation time needed to perform them, the computational power needed to perform them, and the degree to which the result can be shown to compare to an optimum result. Moreover, techniques that are known to be useful in some situations, such as primal-dual solutions, or randomized rounding solutions, cannot generally be extended in any straightforward manner to more complicated networks' additional variables.
Accordingly, there is a need to provide an approximation algorithm for use in network design methods that can provide solutions when network design criteria correspond to a PCSF or a PCSSN. There is a further need to provide such an approximation algorithm that further has a suitable approximation factor, that can use existing LP-solvers, and that can find solutions using reasonable computational resources in a reasonable time.